/*
@Author: bevin

@Created on: 2017-01-29 09:56:17
*/
package main

import (
	"fmt"
)

func main() {
	fmt.Println(combination(40, 20))
	//fmt.Println(getFactors(20))
}

func getFactors(num int, factors *map[int]int) {
	for num != 1 {
		for i := 2; i <= num; i++ {
			if num%i == 0 {
				(*factors)[i]++
				num /= i
				break
			}
		}
	}
}

func diffFactors(numerator *map[int]int, denominator *map[int]int) {
	for k, v := range *denominator {
		if (*numerator)[k] >= v {
			(*numerator)[k] -= v
			delete(*denominator, k)
		} else {
			(*denominator)[k] -= (*numerator)[k]
			delete(*numerator, k)
		}
	}
}

func combination(m int, n int) int {
	result := 1
	numerator := make(map[int]int)
	denominator := make(map[int]int)
	for i := n; i >= 1; i-- {
		getFactors(m+i-n, &numerator)
		getFactors(i, &denominator)
	}
	diffFactors(&numerator, &denominator)
	for k, v := range numerator {
		for i := 0; i < v; i++ {
			result *= k
		}
	}
	for k, v := range denominator {
		for i := 0; i < v; i++ {
			result /= k
		}
	}
	fmt.Println(numerator)
	fmt.Println(denominator)
	return result
}
